package com.example.javalib.math;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * @Description:
 * @author: zcs
 * @email: 1059737741@qq.com
 * create at 2022/2/14 17:51
 */
public class BinaryTree {


    public static void main(String[] args) {

        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        //iteraOrder(node1);
        List list = new ArrayList();
        level2Order(node1,1,list);
        list = (List) list.stream().filter(it -> it != null).collect(Collectors.toList());
        System.out.println(Arrays.toString(list.toArray()));

        //preOrder2(node1);
        //midOrder(node1);
        //postOrder(node1);

        //levelOrder(node1);

    }

    public static class TreeNode {
        public int val;
        public int deepth;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //迭代
    public static void iteraOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //System.out.println(root.val);//前序遍历 ： 根 左 右
        iteraOrder(root.left);
        //System.out.println(root.val);//中序遍历 ：左 根 右
        iteraOrder(root.right);
        System.out.println(root.val); //后序遍历 ：左 右  根
    }

    //层序遍历 ： 从上到下，从左往右
    public static void level2Order(TreeNode root,int i,List list) {
        if (root == null) {
            return;
        }
        int length = list.size();
        if(length <= i){
            for (int j = 0; j <= i-length ; j++) {
                list.add(j+length,null);
            }
        }
        list.set(i,root.val);
        level2Order(root.left,2*i,list);
        level2Order(root.right,2*i + 1,list);
    }




    // 前序遍历 ： 根 左 右
    public static void preOrder2(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.add(root);

            while (root.left != null) {
                root = stack.pop();

                if (root != null) {
                    System.out.println(root.val);
                    stack.push(root.right);
                    stack.push(root.left);
                }
            }
        }

    }

    // 中序遍历 ：左 根 右
    public static void midOrder(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            //stack.add(root);

            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;

                } else {
                    root = stack.pop();
                    System.out.println(root.val);
                    root = root.right;
                }

            }
        }

    }

    // 后序遍历 ：左 右  根
    public static void postOrder(TreeNode root) {
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode prev = null;
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (root.right == null || root.right == prev) {
                    System.out.println(root.val);
                    prev = root;
                    root = null;
                } else {
                    stack.push(root);
                    root = root.right;
                }

            }

        }

    }

    //层序遍历 ： 从上到下，从左往右
    public static void levelOrder(TreeNode root) {
        if (root != null) {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);

            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                if (node != null) {
                    System.out.println(node.val);
                    q.add(node.left);
                    q.add(node.right);
                }
            }

        }
    }

}
